GATE IT 2008


Q21.

If the time-slice used in the round-robin scheduling policy is more than the maximum time required to execute any process, then the policy will
GateOverflow

Q22.

An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:
GateOverflow

Q23.

Consider the following sequence of nodes for the undirected graph given below: 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which of the above is/are possible output(s)?
GateOverflow

Q24.

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k)=kmod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
GateOverflow

Q25.

What Boolean function does the circuit below realize?
GateOverflow

Q26.

Consider the following Hasse diagrams.i.ii.iii.iv.Which all of the above represent a lattice?
GateOverflow

Q27.

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span?ning Tree?
GateOverflow

Q28.

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?
GateOverflow

Q29.

Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
GateOverflow

Q30.

Consider the following two finite automata. M_1 accepts L_1 and M_2 accepts L_2. Which one of the following is TRUE?
GateOverflow